package 力扣._101_对称二叉树;

import 力扣.公用数据结构.TreeNode;

public class Solution3 {

    //官方题解
    /*我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，
    ppp 指针和 qqq 指针一开始都指向这棵树的根，随后 ppp 右移时，qqq 左移，
    ppp 左移时，qqq 右移。每次检查当前 ppp 和 qqq 节点的值是否相等，
    如果相等再判断左右子树是否对称。
     */
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2_1 = new TreeNode(2);
        TreeNode node2_2 = new TreeNode(2);
        TreeNode node3_1 = new TreeNode(3);
        TreeNode node3_2 = new TreeNode(3);
        node1.left=node2_1;
        node1.right=node2_2;
        node2_1.right=node3_1;
        node2_2.right=node3_2;
        boolean b = new Solution3().isSymmetric(node1);
        System.out.print(b);
    }
}
